﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0084_Exist : IAlgorithm
    {
        // 79. 单词搜索

        // 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
        // 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

        // 提示：
        //  m == board.length
        //  n = board[i].length
        //  1 <= m, n <= 6
        //  1 <= word.length <= 15
        //  board 和 word 仅由大小写英文字母组成

        // 进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

        public void Test()
        {
            // 算法参数定义
            var board = new char[][] {
            new char[]{ 'A','B','C','E' },
            new char[]{ 'S','F','E','S' },
            new char[]{ 'A','D','E','E' }
            };
            //var word = "ABCB";
            var word = "ABCESEEEFS";
            // 算法执行与打印
            Console.WriteLine(Exist(board, word));
            //var res = Algorithm(param);
        }

        int[][] direction = new int[][] { new int[] { 0, -1 }, new int[] { 1, 0 }, new int[] { 0, 1 }, new int[] { -1, 0 } };
        // 算法
        public bool Exist(char[][] board, string word)
        {
            var temp = string.Empty;
            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board[0].Length; j++)
                {
                    var vis = new bool[board.Length, board[0].Length];
                    if (DFS(board, word, vis, i, j, temp))
                        return true;
                }
            }
            return false;
        }
        private bool DFS(char[][] board, string word, bool[,] vis, int i, int j, string temp)
        {
            if (i < 0 || i == board.Length || j < 0 || j == board[0].Length || word[temp.Length] != board[i][j] || vis[i, j])
                return false;
            temp += board[i][j];
            vis[i, j] = true;
            if (temp.Length == word.Length)
                return true;
            for (int k = 0; k < direction.Length; k++)
            {
                if (DFS(board, word, vis, i + direction[k][0], j + direction[k][1], temp))
                    return true;
            }
            vis[i, j] = false;
            return false;
        }

        public bool exist(char[][] board, string word)
        {
            int h = board.Length, w = board[0].Length;
            var visited = new bool[h, w];
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    bool flag = check(board, visited, i, j, word, 0);
                    if (flag)
                        return true;
                }
            }
            return false;
        }
        public bool check(char[][] board, bool[,] visited, int i, int j, string s, int k)
        {
            if (board[i][j] != s[k])
                return false;
            else if (k == s.Length - 1)
                return true;
            visited[i, j] = true;
            foreach (var dir in direction)
            {
                int newi = i + dir[0], newj = j + dir[1];
                if (newi >= 0 && newi < board.Length && newj >= 0 && newj < board[0].Length)
                {
                    if (!visited[newi, newj])
                    {
                        bool flag = check(board, visited, newi, newj, s, k + 1);
                        if (flag)
                            return true;
                    }
                }
            }
            visited[i, j] = false;
            return false;
        }

    }
}
